package com.hot100.mid;

import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;

/**
 * @author zhengTao
 * @version 1.0
 * @description: 最长不重复字串，滑动窗口，方法3更好理解
 * @date 2022/7/17 17:29
 */
public class Demo02 {

    public static void main(String[] args) {
        int pwwkew = lengthOfLongestSubstring("au");
        System.out.println(pwwkew);
    }


    //暴力解法
    public  static int lengthOfLongestSubstring(String s) {
        int max=1;
        if(s==null||"".equals(s)){
            return 0;
        }
        if(s.length()==1){
            return 1;
        }

        for (int i = 0; i < s.length(); i++) {
            HashSet<Character>  charSet=new HashSet<>();
            int count=0;
            for (int j = i; j <s.length() ; j++) {
                char c = s.charAt(j);
                if(charSet.contains(c)){
                    max= Math.max(count, max);
                    break;
                } else {
                    charSet.add(c);
                    count++;
                    if(j ==s.length()-1){
                        max= Math.max(count, max);
                    }
                }
            }
        }
      return max;
    }



    public static int lengthOfLongestSubstring2(String s) {
        // 记录字符上一次出现的位置
        int[] last = new int[128];
        for(int i = 0; i < 128; i++) {
            last[i] = -1;
        }
        int n = s.length();

        int res = 0;
        int start = 0; // 窗口开始位置
        for(int i = 0; i < n; i++) {
            int index = s.charAt(i);
            start = Math.max(start, last[index] + 1);
            res   = Math.max(res, i - start + 1);
            last[index] = i;
        }

        return res;
    }

    //用list模拟一个滑动窗口 ,更好理解
    public static int lengthOfLongestSubstring3(String s) {
        int maxLength = 0;
        List<Character> list = new ArrayList<>();
        for(int i=0;i<s.length();i++){
            if(list.isEmpty()){
                list.add(s.charAt(i));
            }
            if(list.contains(s.charAt(i))){
                //如果list中已经存在当前字符，更新maxLength，更新list，找到那个元素，那个元素之前的都移除出去
                maxLength = Math.max(list.size(), maxLength);
                while(list.get(0)!=s.charAt(i)){
                    list.remove(0);
                }
                //和后面要加进来元素相同，把前一个移出去，新元素加在list最后
                list.remove(0);
            }
            //新元素加在list最后
            list.add(s.charAt(i));
        }
        //由于最后一个字符添加到list中之后就直接跳出了循环，所以这里需要再更新一下maxLength
        maxLength = Math.max(list.size(), maxLength);
        return maxLength;
    }
}
